// https://www.lintcode.com/problem/keyboard-row/

public class Solution {
    /**
     * @param words: a list of strings
     * @return: return a list of strings
     */
    public String[] findWords(String[] words) {
        // write your code here
        List<String> ret = new ArrayList<>();
        HashMap<Character, Integer> map = new HashMap<>();
        initMap(map);
        for (String word : words) {
            String wu = word.toUpperCase();
            int line = -1;
            boolean match = true;
            for (int i = 0; i < wu.length(); ++i) {
                if (line == -1) {
                    line = map.get(wu.charAt(i));
                } else {
                    if (line != map.get(wu.charAt(i))) {
                        match = false;
                        break;
                    }
                }
            }
            if (match) {
                ret.add(word);
            }
        }
        return ret.toArray(new String[ret.size()]);
    }
    
    protected void initMap(HashMap<Character, Integer> map) {
        map.put('Q', 1);
        map.put('W', 1);
        map.put('E', 1);
        map.put('R', 1);
        map.put('T', 1);
        map.put('Y', 1);
        map.put('U', 1);
        map.put('I', 1);
        map.put('O', 1);
        map.put('P', 1);
        map.put('A', 2);
        map.put('S', 2);
        map.put('D', 2);
        map.put('F', 2);
        map.put('G', 2);
        map.put('H', 2);
        map.put('J', 2);
        map.put('K', 2);
        map.put('L', 2);
        map.put('Z', 3);
        map.put('X', 3);
        map.put('C', 3);
        map.put('V', 3);
        map.put('B', 3);
        map.put('N', 3);
        map.put('M', 3);
    }
}